/**
 * 46. 全排列
 * https://leetcode-cn.com/problems/permutations/
 */
const { displayNestedArray } = require('../../libs/public');

function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {number[]} nums
 * @param {number} begin
 * @return {number[][]}
 */
function permuteSub(nums, begin) {
  const numsCopy = Array.from(nums);
  if (begin >= nums.length - 1) {
    return [numsCopy];
  }
  const result = [];
  for (let i = begin; i < numsCopy.length; i += 1) {
    swap(numsCopy, begin, i);
    const children = permuteSub(numsCopy, begin + 1);
    // eslint-disable-next-line prefer-spread
    result.push.apply(result, children);
  }
  return result;
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {
  return permuteSub(nums, 0);
}

console.log(displayNestedArray(permute([1, 2, 3])) === '[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]');
